1. Field of the Invention
This invention relates generally to computer graphics and, more specifically, to wrap deforming a model using subdivision surfaces.
2. Background Art
Computers are widely used to model figures, from insects and monsters to human beings. The basic view of a figure is known as a model. Creating a model requires a lot of time and effort on the part of a user. In general, a user creates a model by scanning in a three-dimensional sculpture or by creating a model by hand based on a traditional two-dimensional drawing. Frequently, a computer-generated (CG) model is represented mathematically by one or more parametric surfaces. A CG model usually comprises a large number of parametric surfaces connected together. A parametric surface is a description of a two-dimensional object in three-dimensional space where every point on the parametric surface can be mapped to a pair of parameters (u, v). Many types of parametric surfaces are used in CG modeling, such as NURBS (Non-Uniform Rational B-Splines) surfaces and subdivision surfaces (the latter having a non-trivial parameterization).
A parametric surface has a set of control points (also known as control vertices or “CVs”) that define the shape of the surface. When a CV is moved, the surface that is defined by the CV deforms into a new shape. Thus, a user can change the shape of a model by moving the CVs that define the model's surfaces. In order to deform a model to a particular shape, a user often must move a large number of CVs, due to the natural constraints of parametric surfaces. Moving large numbers of CVs directly, one by one, is time-consuming and not very intuitive. Instead, users manipulate CVs programmatically through the use of a deformation algorithm (“deformer”). A deformer enables an animator to move CVs indirectly by using a simpler interface.
Many types of deformers exist such as, for example, blendshapes, clusters, and free-form deformers. Free-form deformers partition space into discrete cells. One type of free-form deformer, a lattice, comprises surrounding a model with a polygonal cubic mesh that is partitioned into a relatively large number of divisions in x, y, and z (hence the name “lattice”). The lattice surrounds the model in such a way that each of the model's CVs falls inside one cell of the lattice. As the user moves the vertices of the lattice, the cells of the lattice are deformed, and the CVs located inside the cells get transformed according to a local affine transformation, eventually placing the CVs in new locations. In this way, a relatively low-resolution lattice can be used to create broad deformation on a high-resolution model.
Another type of free-form deformer, a wrap deformer, is similar to a lattice but uses an arbitrary polygonal mesh of free topology rather than a lattice mesh. The polygonal mesh, also known as a polywrap, wrap, or cage, acts as a binding domain for the model, such that the model is bound to the wrap. This binding transmits deformations of the wrap's vertices to the CVs of the model, thereby deforming the model itself. Deformations of the wrap's vertices can affect the model's CVs in a variety of ways. One family of wrap deformers creates small cells in the space surrounded by the wrap and associates the cells with the CVs of a model. The problem with this type of wrap deformer is that it doesn't scale well with the size of the model. Large models at high resolution may require a huge number of cells, and the evaluation and update process of the deformer is very slow and consumes a lot of memory. Conversely, using a smaller number of cells will introduce discretization artifacts in the model during deformation. This type of wrap deformer is further described in “Free-form Deformations with Lattices of Arbitrary Topology” by R. MacCracken and K. Joy, Proceedings of the 23rd International Conference on Computer Graphics and Interactive Techniques, 1996, pp. 181-190.
Another family of wrap deformers associates the CVs of a model with certain CVs on the wrap. The motion of the model's CVs is then defined as a weighted linear combination of the motions of the wrap's CVs. This approach is faster than the space cell division approach mentioned above; however, it suffers from many problems and artifacts due to the simplistic nature of the linear interpolation scheme.
A wrap can be located either inside or outside of a model. When a wrap is located inside a model, it acts like a skeleton. As the underlying skeleton changes, the outer layer (the model) changes also. When a wrap is located outside of a model, it acts like a puppeteer with strings connecting the wrap to the model. As the wrap is deformed, the strings pull on the model and thereby deform the model.
In order to animate a model, it is necessary to create additional images that show the model in various poses corresponding to stages of a movement. Each of these images is identical to the model except for slight differences. For example, the model may have its mouth closed, while additional images show the model's mouth opening over time. Many images must be created in order to animate a detailed model. Creating each image by manually editing each CV of the model is nearly impossible. Not only does it require a great deal of work, it also does not result in a convincing performance for the animated model because of the awkwardness of the interface.
Instead, animators use software “rigs” to pose models as if they were puppets. A rig is a set of joints, skeletons, and deformers that attach to a model. Rigs provide the “machinery” that enables users to animate models. A rig comprises computer modules and interfaces that enable an animator to move the CVs of the model indirectly, via a much simpler interface. For example, a rig enables an animator to select a part of a model, such as an eyebrow or a lip, and use simple user interface widgets, such as buttons and sliders, to move that part of the model.
Existing wrap deformation software, such as Maya® from Alias Systems and SOFTIMAGE®|3D from Avid Technology, Inc., has several disadvantages. One disadvantage is that deformations of the wrap result in excessive linear interpolation artifacts in the model. The changes made to the wrap are often discontinuous due to the wrap's lack of resolution, and these discontinuities end up getting transferred to the model. These artifacts are most noticeable when there is a significant difference between the resolution of the wrap and the resolution of the model. This situation is common because wraps are usually low-resolution (not continuous), whereas models are usually high-resolution (continuous). FIG. 1 shows an example of discontinuities created by wrap deforming a model using prior art software. Here, the wrap 100 is a low-resolution polygonal mesh and the model 110 is a higher-resolution NURBS (Non-Uniform Rational B-Splines) plane. FIG. 1 shows the effect on the model 110 of raising the second row of control vertices in the wrap 100. The artifacts indicate problems with the cell splitting of the polygonal mesh wrap and problems with the weighted contributions of the wrap on the control vertices of the model.
Another disadvantage of prior art software is that it is slow. The slowness is severe enough to make wrap deformation inadequate for character setup purposes. For example, it cannot be used for sculpting new blendshapes from existing models, unless the models are very small and not detailed. When existing software is used to wrap deform a detailed, realistic model, it runs so slowly that it is virtually unusable for modeling and animation. Since free-form deformers partition space into discrete cells, the calculations they perform require O(n3) time, where n is the number of cells.
What is needed is a way to wrap deform a model that results in fewer discontinuities and artifacts and is fast enough to be used for modeling realistic characters and animating characters using rigs.